/*
*
汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。

沿途有加油站，用数组 stations 表示。其中 stations[i] = [positioni, fueli] 表示第 i 个加油站位于出发位置东面 positioni 英里处，并且有 fueli 升汽油。

假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。

为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。

注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。

示例 1：

输入：target = 1, startFuel = 1, stations = []
输出：0
解释：可以在不加油的情况下到达目的地。
示例 2：

输入：target = 100, startFuel = 1, stations = [[10,100]]
输出：-1
解释：无法抵达目的地，甚至无法到达第一个加油站。
示例 3：

输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
输出：2
解释：
出发时有 10 升燃料。
开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。
然后，从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料），
并将汽油从 10 升加到 50 升。然后开车抵达目的地。
沿途在两个加油站停靠，所以返回 2 。

提示：

1 <= target, startFuel <= 109
0 <= stations.length <= 500
1 <= positioni < positioni+1 < target
1 <= fueli < 109

  - @author ala
  - @date 2024-10-07 10:31
*/
package main

import (
	"fmt"
	"math"
)

func main() {
	target, startFuel := 100, 10
	stations := [][]int{{10, 60}, {20, 30}, {30, 30}, {60, 40}}

	fmt.Println(minRefuelStops(target, startFuel, stations))
}

/**
 *	1）stations收尾各补一个加油站，起点[0, startFuel]，终点[target, 0]
 *	2）dp[i][j]表示在第i个加油站，加j次油的最大剩余油量
 *		dp[0][0] = startFuel
 *	3）如果dp[i][j]的剩余油量能跑到i+1，则可以选择在i+1处是否加油
 *		d：i 跑到 i+1 的里程数
 *		不加油：dp[i + 1][j] = dp[i + 1][j] - d
 *		加油：dp[i + 1][j + 1] = dp[i + 1][j] - d + startFuel[i - 1][1]
 *		过程中如果所有加油次数都不能跑到i+1，直接g
 *	4）最后检测在第 i+1 个加油站（终点），剩余油量 >= 0的最小加油次数就是答案
 */
func minRefuelStops(target int, startFuel int, stations [][]int) int {
	N := len(stations)
	//	首尾各补一个加油站
	dp := make([][]int, N+2)
	for i := range dp {
		dp[i] = make([]int, N+2) //	最后一个加油站（终点）也可以选择加油，虽然加油量为0
	}
	dp[0][0] = startFuel

	prev := 0
	for i := 1; i <= N+1; i++ {
		//	第i个加油站的里程数
		crt := 0
		if i == N+1 {
			crt = target
		} else if i > 0 {
			crt = stations[i-1][0]
		}
		d := crt - prev
		prev = crt
		//	第i个加油站的油量
		fuel := 0
		if i == N+1 {
			fuel = 0
		} else if i > 0 {
			fuel = stations[i-1][1]
		}

		//	检测从 i-1 能否跑到 i（在 i-1 个加油站，最多加 i-1 次油）
		//	如果能跑到，则在第i个加油站选择：加油 或 不加油
		succ := false
		for j := 0; j < i; j++ {
			if (dp[i-1][j] < 0) || (dp[i-1][j]-d < 0) {
				dp[i][j] = INF
			} else {
				succ = true
				dp[i][j] = max(dp[i][j], dp[i-1][j]-d)
				dp[i][j+1] = max(dp[i][j], dp[i-1][j]-d+fuel)
			}
		}
		//	如果所有加油次数全歇菜，那回家洗洗睡吧
		if !succ {
			return -1
		}
	}
	//	检测在第 N+1 个加油站（终点），剩余油量 >= 0 的最小次数
	for j := 0; j <= N; j++ {
		if dp[N+1][j] >= 0 {
			return j
		}
	}
	return -1
}

var (
	INF int = math.MinInt32 >> 1
)
